#include<iostream>
#include<queue>
#include<vector>
using namespace std;
typedef pair<int, int> PII;
#define x first;
#define y second
const int N = 1e5 + 10, M = N * 10;
int h[N], e[M], ne[N], w[M];
bool st[N];
int n, m;
int dij()
{
	priority_queue<PII, vector<PII>, greater<PII>>heap;
	heap.push({ 1,0 });
	while (!heap.empty()) {
		PII t = heap.top();
		heap.pop();
		if (st[t.x]) {
			continue;
		}
		st[t.x] = 1;
		for(int i=h[t.x];`i;i=ne[i]){
			int j=e[i];
			if(dis[j]>dis[t.x]+w[i]){
				dis[j]=dis[t.x]+w[i];
				if(!st[j]){
					heap.push({j,dis[j]}));
				}
			}
		}
	}
}
int main()
{
	
	return 0;
}
